package ast_generator;

import java.util.ArrayList;
import java.util.Stack;
import java.util.HashMap;

import javax.management.RuntimeErrorException;

/**
 * 
 * @author Chu
 *This class creates a recursive descent parser using the grammar specified in the book. Check the readme for more information about what the recursive descent parser can handle
 */
public class RecursiveDescentParser {
ArrayList<String> concat;
String regex;
String tempCharClass;
Stack<String> backup;
HashMap<String,ArrayList<String>> characterClasses;	

public RecursiveDescentParser(String r,HashMap c)
{
	backup = new Stack<String>();
	concat=new ArrayList<String>();
	concat.add("concat");
	 regex=r;
	 String s=r.substring(0);
	 backup.push(s);
	 characterClasses=c;
}
public ASTNode parse(){
	//ASTNode headnode= new ASTNode();
	backup.push(regex.substring(0));
	try{
	ASTNode node= new ASTNode();
	node.setOperation(true);
	ASTNode left=rexp1();
	ASTNode right=rexpb();
	node.setLeft(left);
	node.setRight(right);
	if(right.getValue()==null)
	{
		ArrayList<String> temp= new ArrayList<String>();
		temp.add("|");
		node.setValue(concat);
	
	}
	else
	{
		ArrayList<String> temp= new ArrayList<String>();
		temp.add("|");
		node.setValue(temp);
	}
	backup.push(regex);
	return node;
	}
	catch(Exception e)
	{
		regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "token doesn't match rexp1 ");	

	}
	//return headnode;
}
private ASTNode rexpb() { //return a tree with a union symbol, or epsilon
	backup.push(regex.substring(0));

	try{
		String token=match("UNION");
		regex=regex.substring(token.length());//consume the token, I can get away with thisb/c only a right hand expression
		/*rexp1();
		rexpb();*/
		ASTNode node=parse();
		backup.push(regex);
		return node;
	   }
	catch (Exception e){
		return new ASTNode();
		//return epsillon
	}
}
private ASTNode rexp1() {
   backup.push(regex.substring(0));
   try{
   ASTNode node= new ASTNode();
   node.setOperation(true);
   node.setValue(concat);	   
   ASTNode left= rexp2();
   ASTNode right=rexp1b();
   node.setLeft(left);
   if(right.getValue()==null)
   {
	   node=left;
   }
   else node.setRight(right);
   backup.push(regex);
   return node;
   }
   catch(Exception e)
   {
	   regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "token doesn't match rexp1 ");	

   }
}

private ASTNode rexp1b() {
	//backup.push(regex.substring(0));
	
	backup.push(regex.substring(0));
	try{
	ASTNode node= new ASTNode();
	node.setOperation(true);
	node.setValue(concat);
	ASTNode left=rexp2();
	if(left.getValue()==null)
	{
		node=new ASTNode();
	}
	else{
		node.setLeft(left);
	node.setRight(rexp1b());
	}
	backup.push(regex);
	return node;
	}
	catch(Exception e)
	{

		return new ASTNode();
		//return epsillon

	}
	
}

private ASTNode rexp2() {
	backup.push(regex.substring(0));

	try{
		String token=match("(");
		regex=regex.substring(token.length());//consume the token
		ASTNode subTree=parse();
		token= match(")");
		regex=regex.substring(token.length());//consume the token
		ASTNode operationNode=rexp2tail();
		backup.push(regex);

		if(operationNode.isOperation())
		{
			operationNode.setLeft(subTree);
			operationNode.setRight(new ASTNode());
			return operationNode;
		}
		else
		{
			/*ASTNode parent= new ASTNode();
			parent.setOperation(true);
			parent.setLeft(subTree);
			parent.setRight(new ASTNode());*/
			return subTree;
		}
		
	}
	catch (Exception a)
	{
		regex=backup.peek();

		try{
			String token=match("RE");
			regex=regex.substring(token.length());//consume the token
			ArrayList<String> value= new ArrayList<String>();
			if(token.length()==1) value.add(token);
			else value.add(token.substring(1,2));
			ASTNode left= new ASTNode();
			left.setValue(value);
			int i=token.length();
			
			ASTNode operationNode=rexp2tail();
			backup.push(regex);
			if(operationNode.isOperation())
			{
				operationNode.setLeft(left);
				operationNode.setRight(new ASTNode());
				return operationNode;
			}
			else
			{
				/*ASTNode parent= new ASTNode();
				parent.setValue(concat);
				parent.setOperation(true);
				parent.setLeft(left);
				parent.setRight(new ASTNode());
				return parent;*/
				return left;
			}
		}
		catch (Exception b)
		{
			regex=backup.peek();
			try{
				ASTNode node=rexp3();
				backup.push(regex);
				return node;
			}
			catch(Exception c)
			{
				regex=backup.pop();
				//need to do something maybe? might throw exception
				throw new RuntimeErrorException(new Error(), "token doesn't match rexp2tail ");	

			}
		}
	}
}


private ASTNode rexp2tail() {
	backup.push(regex.substring(0));
	ArrayList<String> list= new ArrayList<String>();
	try{
		String token=match("*");
		regex=regex.substring(token.length());//consume the token
		backup.push(regex);
		ASTNode node =new ASTNode();
		ArrayList<String> value= new ArrayList<String>();
		value.add(token);
		node.setValue(value);
		node.setOperation(true);
		return node;
	}
	catch (Exception a)
	{ regex=backup.peek();
		try{
			String token=match("+");
			regex=regex.substring(token.length());//consume the token
			backup.push(regex);
			ASTNode node =new ASTNode();
			ArrayList<String> value= new ArrayList<String>();
			value.add(token);
			node.setValue(value);
			node.setOperation(true);
			return node;
			
		}
		catch(Exception b)
		{
		return new ASTNode();
			//return epsillon might throw exception

		}
	}
	
	
}

private ASTNode rexp3() {
	backup.push(regex.substring(0));
	try
	{
		ASTNode node=charclass();
		backup.push(regex);
		return node;
	}
	catch (Exception a)
	{
		ASTNode node=new ASTNode();//return epsilon node.

		return node;
		// return epsillon

	}
}

private ASTNode charclass() { //pretty sure this effectively always returns a leafnode
	backup.push(regex.substring(0));
  try{
	  String token=match("."); //if succeeds, this is a leaf node.
	  regex=regex.substring(token.length());
		backup.push(regex);
	  ArrayList<String> allChars=new ArrayList<String>();
	  for(int i=32;i<127;i++)//did not include ACII values of commands in list
	  {allChars.add(Character.toString((char)i));
	  };
	  ASTNode node= new ASTNode();
	  node.setValue(allChars);//operations is fals, left right node are false
	  return node;
  }
  catch (Exception b)
  {
	  regex=backup.peek();
	 try {
	 String token= match("[");
	 regex=regex.substring(token.length());
	 ASTNode node= charclass1();
		backup.push(regex);
	  return node;
	 }
	 catch(Exception e)
	 {
		 try
		 {
			 regex=backup.peek();
		 ASTNode node=definedclass();
			backup.push(regex);
		 return node;
		 }
		 catch(Exception f)
		 {
			 regex=backup.pop();
				throw new RuntimeErrorException(new Error(), "nothing works ");	

		 }
	 }
  }
}
private ASTNode charclass1() {
	backup.push(regex.substring(0));
	try{
		ASTNode node= charsetlist();
		backup.push(regex);
		return node;
		}
	catch(Exception a)
	{
		try{
			regex=backup.peek();
			ASTNode node= excludeset();
			backup.push(regex);
			return node;
		}
		catch(Exception b)
		{
			regex=backup.pop();
			throw new RuntimeErrorException(new Error(), "nothing works ");	
			
		}
	}
}



private ASTNode charsetlist() {
	backup.push(regex.substring(0));
	try{
		ASTNode parentNode= new ASTNode();
		//concat charset and charsetlist
		parentNode.setOperation(true);
		ArrayList<String> temp= new ArrayList<String>();
		temp.add("|");
		parentNode.setValue(temp);
		parentNode.setLeft(charset());//returns either a single character node or a range of chars
		parentNode.setRight(charsetlist());//concat with potentially more single nodes or range of chars
		if(parentNode.getRight().getValue()==null)
		{
			parentNode.setValue(concat);
		}
		backup.push(regex);
		return parentNode;
	}
	catch(Exception e)
	{
		backup.peek();
		try{
			String token=match("]");
			regex=regex.substring(token.length());
			backup.push(regex);
			return new ASTNode();
		}
		catch (Exception b)
		{
			regex=backup.pop();
			throw new RuntimeErrorException(new Error(), "nothing works ");	

		}
	}
}
private ASTNode charset() {
	backup.push(regex.substring(0));
	try{
		String token=match("CLS");
		regex=regex.substring(token.length());
		ASTNode node = charsettail(token);
		backup.push(regex);
		if(node.getValue()==null)//if epsilon, just return the singular character
		{
			ASTNode simple=new ASTNode();
			ArrayList<String> temp=new ArrayList<String>();
			temp.add(token);
			simple.setValue(temp);
			return simple;
		}
		else //return the set
		{
			return node;
		}
		
	}
	catch(Exception e)
	{
		regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "nothing works ");	

	}
}
private ASTNode charsettail(String in) {
	backup.push(regex.substring(0));
	try{
		String token=match("-");
		regex=regex.substring(token.length());
		token=match("CLS");
		regex=regex.substring(token.length());
		if(token.length()==1);
		else  token.substring(1,2);
		int start= in.charAt(0);
		int end= token.charAt(0);
		ArrayList<String> set= new ArrayList<String>();
		while(start<=end)
		{
			set.add(Character.toString((char)start));
			start++;
		}
		backup.push(regex);
		ASTNode node= new ASTNode();
		node.setValue(set);
		return node;
	}
	catch(Exception e)
	{

		return new ASTNode();
		//epsilon
	}
	
}
private ASTNode excludeset() {
	backup.push(regex.substring(0));
	try{
		String token=match("^");
		regex=regex.substring(token.length());
		ArrayList<String> excluded=charset().getValue();
		token=match("]");
		regex=regex.substring(token.length());
		token=match("IN");
		regex=regex.substring(token.length());
		ArrayList<String> excluded2=excludesettail().getValue();
		for(int i=0;i<excluded.size();i++)
		{
			if(excluded2.contains(excluded.get(i)))
			{
				excluded2.remove(excluded.get(i));
			}
			else;
		}
		ASTNode node= new ASTNode();
		node.setValue(excluded2);
		backup.push(regex);
		return node;
	}
	catch (Exception e)
	{
		regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "nothing works ");	

	}
}
private ASTNode excludesettail() {
	backup.push(regex.substring(0));
	try{
		String token=match("[");
		regex=regex.substring(token.length());
		ASTNode node =charset();
		token=match("]");
		regex=regex.substring(token.length());
		backup.push(regex);
		return node;
	}
	catch (Exception e)
	{
		regex=backup.peek();
		try{
		ASTNode node =definedclass();
		backup.push(regex);
		return node;
		}
		catch(Exception b)
		{
		regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "nothing works ");	

		}
	}
}
private ASTNode definedclass() { //returns AST leafnode containing a defined characterclass
 regex=backup.push(regex.substring(0))	;
 try{
	String token= match("DEFINED");
	regex=regex.substring(token.length());
	backup.push(regex);
	 ASTNode node= new ASTNode();
	 node.setValue(characterClasses.get(token));//rest values are false
	 return node;
 }
 catch(Exception e)
 {
	 regex=backup.pop();
		throw new RuntimeErrorException(new Error(), "nothing works ");	

 }
}
private String peekToken() //do i need this in addition to match? yeah use match(peekToken(),String)
{
	if(regex.length()<1)
	{
		
		throw new RuntimeErrorException(new Error(), "regex Empty");

	}
	else
	{
		String s=Character.toString(regex.charAt(0));//get the first character into s
	   if(s.equals("\\")) //check if it has an escape character
		{
	
			if(regex.length()<2)
			{
				throw new RuntimeErrorException(new Error(), "regex Empty, invalid escape");
			}
			else{
			
			     return regex.substring(0,2);

				}
		}
	   else if(s.equals(" ")||s.equals("\t")||s.equals("\n"))
	   {
		   regex=regex.substring(1);
		   return peekToken();
	   }
		else
		{
			return s;
		}
	}
	
}
private void consumeToken() //consume token, may not be necessary, one line of code.
{
	
}

private String match( String grammarToken){ //compare token from regex string, to a string in the grammar
	String token=peekToken();
	if(token.length()>0 && !token.equals(null))
	{
	if(grammarToken.length()==1)	//case where grammar token is just a string of length 1 that needs to be matched
	{
		if(token.equals(grammarToken))
		{
			return token;
		}
		else
		{
			throw new RuntimeErrorException(new Error(), "Single character match fail");
		}
	}
	else if (grammarToken.equals("DEFINED"))
	{
		if(token.equals("$"))
		{
			int i=0;
			
			while( i<=regex.length())
			{
				String t = regex.substring(0,i);
				if(characterClasses.containsKey(regex.substring(0,i)))
				{
						return regex.substring(0,i);
				}
				i++;
			}
		}
		throw new RuntimeErrorException(new Error(), "Not a defined class");

	}
	else if (grammarToken.equals("IN"))
	{
		if(token.equals("I"))
		{
			if(regex.substring(1,2).equals("N"))
			{
				return regex.substring(0,2);
			}
		}
		throw new RuntimeErrorException(new Error(), "Not an IN");

	}
	else if (grammarToken.equals("UNION"))
	{
		if(token.equals("|"))
		{
			return token;
		}
		else
			throw new RuntimeErrorException(new Error(), "Not a UNION Character");
	}
	else if (grammarToken.equals("CLS"))
	{ 
		if(token.length()==1)
		{
			if(!(token.equals("\\")||token.equals("^")||token.equals("-")||token.equals("[")||token.equals("]")))//need to check other things including $
			{
				return token;
			}
			else
			{
				throw new RuntimeErrorException(new Error(), "CLS: Can't just be a \\");
			}
		}
		else if(token.length()==2)
		{
			if(token.equals("\\\\")||token.equals("\\^")||token.equals("\\-")||token.equals("\\[")||token.equals("\\]"))
			{
			    return  token.substring(1,2);
			}
			else 
			{
				throw new RuntimeErrorException(new Error(), "CLS: Didn't Match");
			}
		}
		else
		{
			throw new RuntimeErrorException(new Error(), "CLS: cannot match a token of length greater than 2");
		}
	}
		
	else if(grammarToken.equals("RE"))//need to check other things including $
	{
		if(token.length()==1)
		{
			if(!(token.equals("\\")||token.equals("*")||token.equals("+")||token.equals("?")||token.equals("|")||token.equals("[")||token.equals("]")||token.equals("(")||token.equals(")")||token.equals(".")||token.equals("'")||token.equals("\"")||token.equals("$")))	{
						return token;
				}
				else
				{
						throw new RuntimeErrorException(new Error(), "RE : Can't just be a \\");
				}
		}
		else if(token.length()==2)
		{
		    //if the token is an escape character return true, else error out
			if(token.equals("\\\\")||token.equals("\\*")||token.equals("\\+")||token.equals("\\?")||token.equals("\\|")||token.equals("\\[")||token.equals("\\]")||token.equals("\\(")||token.equals("\\)")||token.equals("\\.")||token.equals("\\'")||token.equals("\\\"")||token.equals("\\$"))
			{
			return token;
			}
			else
			{
			throw new RuntimeErrorException(new Error(), "RE: Didn't Match escaped character");
			}
		}
		else
			throw new RuntimeErrorException(new Error(), "RE: cannot match a token of length greater than 2");
	}
	else
		throw new RuntimeErrorException(new Error(), "Not sure how to match");
	}
	else
		throw new RuntimeErrorException(new Error(), "token less than 0 or null");	

	

}
public String toString()
{
	return regex;
}
}
